BM13 判断一个链表是否为回文结构

https://www.nowcoder.com/practice/3fed228444e740c8be66232ce8b87c2f

快慢指针的简单做法

其实快慢指针的做法和最下面的暴力解法差不多，只不过这里是用快慢指针来找到中间节点，然后再判断是否为回文结构

func isPail(head *ListNode) bool {
    if head == nil || head.Next == nil {
        return true
    }

    count, pre := 0, head
    for pre != nil {
        count++
        pre = pre.Next
    }

    var tmp []int
    // 快慢指针
    fast, low := head, head
    for fast != nil && fast.Next != nil {
        tmp = append(tmp, low.Val)
        low = low.Next
        fast = fast.Next.Next
    }

    if (len(tmp) * 2) < count {
        low = low.Next
    }

    for i := len(tmp) - 1; i >= 0; i-- {
        if low == nil || low.Val != tmp[i] {
            return false
        }
        low = low.Next
    }

    return true
}

更优雅的做法：

func isPail(head *ListNode) bool {
    if head == nil || head.Next == nil {
        return true
    }

    var nums []int
    for head != nil {
        nums = append(nums, head.Val)
        head = head.Next
    }

    i, j := 0, len(nums)-1
    for i < j {
        if nums[i] != nums[j] {
            return false
        }

        i++
        j--
    }

    return true
}

暴力解法

直接把链表的值复制到数组中，然后用双指针判断是否为回文结构

func isPail(head *ListNode) bool {
    if head == nil || head.Next == nil {
        return true
    }

    end, size := head, 0
    for end != nil {
        size++
        end = end.Next
    }

    end = head
    middle := size / 2
    var leftArr, rightArr []int
    for i := 0; i < size; i++ {
        if i < middle {
            leftArr = append(leftArr, end.Val)
        } else {
            rightArr = append(rightArr, end.Val)
        }
        end = end.Next
    }

    for i := range leftArr {
        // 这里的 size%2 是为了偶数加一
        if leftArr[i] != rightArr[middle-i-1+size%2] {
            return false
        }
    }

    return true
}